package org.fuys.coder.domain.act.lottery.service.algorithm.impl;

import org.fuys.coder.common.entity.Pair;
import org.fuys.coder.domain.act.lottery.service.algorithm.BaseOddAlgorithm;
import org.fuys.coder.domain.act.lottery.service.strategy.factory.LotteryStrategyFactory;
import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @projectName: fuys-low-coder
 * @package: org.fuys.coder.domain.lottery.service.algorithm.impl
 * @className: AlienBillAlgorithm
 * @author: WangJing
 * @description: 轮盘赌算法 随机抽奖算法之一 时间复杂度为O(n)
 * @date: 2024/7/7 23:17
 * @version: 1.0
 */
@Service
public class AlienBillAlgorithm implements BaseOddAlgorithm {
    private Random random=new Random();
    //注意 当此抽奖活动预计不会太火热的时候 采用此算法 因为此算法不会需要概率信息映射到新数组并长期存储
    @Override
    public Integer randomDraw(Pair<Integer,Integer> type) {
        final List<Pair<Integer, Double>> odds = LotteryStrategyFactory.getStrategyOddInfo(type.getLeft(), type.getRight());
        int total=0;
        List<Integer> weights=new ArrayList<>();
        for (Pair<Integer, Double> odd : odds) {
            final Double right = odd.getRight();
            total+=right*100;
            weights.add(total);
        }
        final int rand = random.nextInt(total);
        return binarySearch(rand,weights);
    }

    private int binarySearch(int target,List<Integer> weights){
        int left=0,right=weights.size()-1;
        while (left<right){
            int mid=left+(right-left)/2;
            if(weights.get(mid)<target){
                left=mid+1;
            }else {
                right=mid;
            }
        }
        return left;
    }
}
